package 算法练习;

import java.util.HashSet;
import java.util.Scanner;

/**
 * 
 * @author ：soulstones
 * @version ：2019年8月15日 下午5:28:40 @Description：
 *          输入两个数n,m;(1<=n<=2000,1<=m<=100);分别表示n次看花，m表示一共有m中花儿。
 *          接下来输入n个数a[1]~a[n]，a[i]表示第i次，小明看的花的种类;
 *          输入一个数Q(1<=Q<=1000000);表示小红的问题数量。 输入Q行 每行两个数 l,r(1<=l<=r<=n);
 *          表示小红想知道在第l次到第r次，小明一共看了多少不同的花儿。 输入样例： 5 3 1 2 3 2 2 3 1 4 2 4 1 5
 *          输出样例： 3 2 3
 * 
 */
public class 看花 {

	static final int max = 2000;
	static int flower[] = new int[max];
	static int n, m, q;
	static int[][] kinds = new int[max][max];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			flower[i] = sc.nextInt();
		}
		getKindTable();
		q = sc.nextInt();
		for (int i = 0; i < q; i++) {
			int l, r;
			l = sc.nextInt();
			r = sc.nextInt();
			System.out.println(getAns(l, r));
		}
		sc.close();
	}

	public static void getKindTable() {
		HashSet set = new HashSet();
		for (int i = 0; i < n; i++) {
			set.clear();
			for (int j = 0; j <= n; j++) {
				set.add(flower[j]);
				kinds[i][j] = set.size();
			}
		}
	}

	public static int getAns(int l, int r) {
		if (l > r) {
			int t = l;
			l = r;
			r = t;
		}
		return kinds[l][r];
	}

}
